package strmatch

// 字符串匹配
//
// 单模式匹配：
// n为主串长度，m为模式串长度
//
// BF(Brute Force)
// 朴素匹配算法，也叫暴利匹配算法
// O(n * m)
//
// RK(Rabin-Karp)
// 通过hash算法优化BF的比较过程
// O(n)
//
// BM(Boyer-Moore)
// 从右即末尾开始匹配
//
// 包含两部分：
// 1.坏字符规则(bad character rule)
// 最好情况O(n/m)
// 在模式串中匹配不到的字符为坏字符，需要跳过，跳过后接着匹配。
//
// 2.好后缀规则(good suffix shift)
// 匹配了一部分的字符为好后缀，寻找模式串相同的段，或者部分相同的段
// 向右滑动进行对接，再接着匹配
//
// 当字符不匹配是，计算两种规则，取移动位数最大的规则执行滑动
// （可以避免坏字符规则滑动位数为负数的问题）
//
// KMP(Knuth Morris Pratt)
// 在BM的基础上添加了好前缀规则，让每次匹配下一个目标字符时移动的次数更少。
//
//
// 多模式匹配：
// 即一个主串，匹配多个模式串。
//
// Trie树
// 对应单模式匹配中的BF算法
//
// AC自动机
// 对应单模式匹配中的KMP算法。
